package sort.leetcode;

/**
 * 剑指offer51号问题，求数组的逆序对个数
 * @author yuisama
 * @date 2022/02/17 19:22
 **/
public class Offer51 {
    public int reversePairs(int[] nums) {
        return reversePairsInternal(nums,0,nums.length - 1);
    }

    /**
     * 在nums的[l..r]区间中，求逆序对的个数
     * @param nums
     * @param l
     * @param r
     * @return
     */
    private int reversePairsInternal(int[] nums, int l, int r) {
        // 终止条件
        if (l >= r) {
            // 此时数组只有一个元素，不存在逆序对
            return 0;
        }
        // 将数组不断拆分
        int mid = (l + r) >> 1;
        // 分别求出左半区间和右半区间的逆序对个数
        int leftNum = reversePairsInternal(nums,l,mid);
        int rightNum = reversePairsInternal(nums,mid + 1,r);
        if (nums[mid] > nums[mid + 1]) {
            // 此时左半区间还有元素大于右半区间，需要merge
            // 整个数组的逆序对个数 = 左区间个数 + 右区间个数 + 本次merge的逆序对个数
            return leftNum + rightNum + merge(nums,l,mid,r);
        }else {
            // 此时nums[mid] < nums[mid + 1]
            // 说明此时整个数组已经有序，不用再merge
            // 整个数组的逆序对个数就是左区间个数 + 右区间个数
            return leftNum + rightNum;
        }
    }

    /**
     * 归并排序的merge过程，返回当前合并后逆序对的个数
     * @param nums
     * @param l
     * @param mid
     * @param r
     * @return
     */
    private int merge(int[] nums, int l, int mid, int r) {
        int ret = 0;
        int[] temp = new int[r - l + 1];
        // 将原数组的元素拷贝到temp
        for (int i = l; i <= r; i++) {
            temp[i - l] = nums[i];
        }
        // 开始合并
        int i = l;
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 左半区间处理完毕
                nums[k] = temp[j - l];
                j ++;
            }else if (j > r) {
                // 右半区间处理完毕
                nums[k] = temp[i - l];
                i ++;
            }else if (temp[i - l] <= temp[j - l]) {
                // 左半区间元素 <= 右半区间元素，此时不构成逆序
                nums[k] = temp[i - l];
                i ++;
            }else {
                // 左半区间元素 > 右半区间元素，此时构成逆序
                ret += (mid - i + 1);
                nums[k] = temp[j - l];
                j ++;
            }
        }
        return ret;
    }
}